
static int maxVal = 0;
// 需要基于贪心剪枝进行优化
void DFS(int *nums, int numsSize, int sum, int idx, int preNumGet)
{
    // DFS的边界
    if (idx == (numsSize - 1))
    {
        // 最后一个元素的前一个值没有取，该值就可以取
        if (preNumGet == 0)
        {
            sum += nums[idx];
        }
        // 更新最大金额
        if (sum > maxVal)
        {
            maxVal = sum;
        }
        return;
    }

    // 如果上一个边界没有取值,两种选择，这轮取或者不取
    if (preNumGet == 0)
    {
        // 选择这轮取
        DFS(nums, numsSize, sum + nums[idx], idx + 1, 1);
        // 选择这轮不取
        DFS(nums, numsSize, sum, idx + 1, 0);
    }
    else
    {
        //上一轮选过，这轮只能跳过
        DFS(nums, numsSize, sum, idx + 1, 0);
    }
    return;
}

int rob(int *nums, int numsSize)
{
    maxVal = 0;
    if (numsSize <= 0)
    {
        return maxVal;
    }
    DFS(nums, numsSize, 0, 0, 0);
    return maxVal;
}